"""
LeetCode 热题

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
"""

class Solution(object):
    def trap(self, height):
        """
        计算按此排列的柱子，下雨之后能接多少雨水。

        参数:
        height (List[int]): 整数数组，表示每个柱子的高度

        返回:
        int: 能接住的雨水总量
        """
        # 如果输入的数组为空，则返回0
        if not height:
            return 0

        # 初始化左右指针
        left, right = 0, len(height) - 1
        # 初始化左右最大高度
        left_max, right_max = 0, 0
        # 初始化雨水总量
        water_trapped = 0

        # 使用双指针法计算雨水总量
        while left < right:
            # 如果左边柱子的高度小于右边柱子的高度
            if height[left] < height[right]:
                # 更新左边最高的柱子
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    # 累加左边柱子能接的雨水量
                    water_trapped += left_max - height[left]
                # 左指针向右移动
                left += 1
            else:
                # 更新右边最高的柱子
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    # 累加右边柱子能接的雨水量
                    water_trapped += right_max - height[right]
                # 右指针向左移动
                right -= 1

        # 返回能接住的雨水总量
        return water_trapped


if __name__ == '__main__':
    a = Solution()
    print(a.trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))



